package com.da.javatest.niuke.baodian;

/**
 * @author chenlida
 * @date 2020/10/11 18:20
 * https://www.nowcoder.com/practice/11b018d042444d4d9ca4914c7b84a968?tpId=8&tags=&title=&diffculty=0&judgeStatus=0&rp=1
 */
public class C52Joseph {
    /**
     * 存在递推公式：
     * f(n,m)表示n个人报数m的离开，最后留下来的人的初始号码
     * f(n,m) = (f(n-1,m)+m)%n;
     */
    public int getResult(int n, int m) {
        if (n < 1 || m < 1) {
            return -1;
        }
        int last = 0;
        if (n == 1) {
            // 最后一轮出局的人肯定是最后轮的第0个，要找到其初始号码
            return last;
        }
        for (int i = 2; i <= n; i++) {
            // 最后出来的人在倒数第i轮的号码是last
            last = (last + m) % i;
        }
        // 注意编号是1-n编号的，而算法是从0~n-1排序的
        return last + 1;
    }

    public static void main(String[] args) {
        C52Joseph test = new C52Joseph();
        System.out.println(test.getResult(5, 3));
    }
}
